package sort.on2;

/**
 * 插入排序：向有序的序列中插入新的元素，新的元素大于所有的就放到最后，否则插入当中，后续元素向后移动
 * 稳定、原地排序
 *
 * @author yeyangtao created at 15:25 2020/9/25
 */
public class InsertionSort {
    public static void insertionSort(int[] a) {
        int size = a.length;
        for (int i = 1; i < size; i++) {
            int value = a[i];
            int j = i - 1;
            //查找要插入的位置
            for (; j >= 0; j--) {
                if (a[j] > value) {
                    //数据移动
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            //插入数据
            a[j + 1] = value;
        }
    }
}
